﻿#include <iostream>
using namespace std;

struct ListNode
{
    ListNode(int _val = -1)
        :next(nullptr)
        , val(_val)
    {}

    struct ListNode* next;
    int val;
};

// 705. 设计哈希集合
// 优化：使用vector容器作为哈希容器
class MyHashSet 
{
public:
    MyHashSet() 
    {
        root = new ListNode();
    }

    void add(int key) 
    {
        ListNode* node = new ListNode(key);
        node->next = root->next;
        root->next = node;
    }

    void remove(int key) 
    {
        ListNode* prev = root;
        ListNode* cur = prev->next;
        while (cur)
        {
            if (cur->val == key)
            {
                prev->next = cur->next;
                delete(cur);
                break;
            }
            prev = cur;
            cur = cur->next;
        }

    }

    bool contains(int key) 
    {
        ListNode* cur = root->next;
        while (cur)
        {
            if (cur->val == key)
                return true;
            cur = cur->next;
        }
        return false;
    }

    ListNode* root;
};

int main()
{
    MyHashSet m;
    m.add(1);
    m.add(2);
    cout << m.contains(1) << endl;
    cout << m.contains(3) << endl;
    m.add(2);
    cout << m.contains(2) << endl;
    m.remove(2);
    cout << m.contains(2) << endl;

    return 0;
}